A plurality of video coding standards have been developed for compressing video data. Such video coding standards include, for example, the ITU-T standards denoted as H.26x, produced by the telecommunication standardization sector of the International Telecommunication Union, and the ISO/IEC standards denoted as MPEG-x. The most up-to-date and advanced video coding standard is currently the standard denoted as H.264/AVC or MPEG-4 AVC (see Non-Patent Literature 1 and Non-Patent Literature 2).
In the H.264/AVC standard, the coding process roughly includes prediction, transform, quantization, and entropy coding. Through the entropy coding, redundant information is cut from information which is used in the prediction, quantized information, and the like. The known examples of the entropy coding include variable-length coding, adaptive coding, and fixed-length coding. The variable-length coding includes Huffman coding, run-length coding, and arithmetic coding.
Of these, the arithmetic coding is a method in which the probability of occurrence of a symbol is calculated to determine an output code. In other words, arithmetic coding is performed on image data using a symbol occurrence probability for each context corresponding to characteristics of image data, while a symbol occurrence probability is updated for each coding. Since a code is determined according to characteristics of image data in the arithmetic coding, the arithmetic coding is known for higher coding efficiency than Huffman coding or the like which uses a fixed coding table.